Electronic assets are digital representations of value. Electronic assets might be used to represent cash, coins, tokens, coupons, entertainment tickets, government entitlement provisions, and so on. Electronic assets are long, mostly random binary strings, with some relatively small recognizable pattern that are signed by an issuer. For instance, an electronic asset might consist of 500 bits in which 400 bits are truly random, 50 bits are an identifiable string (e.g., all binary zeroes), and the remaining 50 bits are an expiration date. The binary strings are typically generated by an institution that issues the electronic assets. Banks, ticket companies, federal or local government, and businesses are all possible issuers of different kinds of electronic assets.
Once issued, the electronic assets are stored in an electronic storage facility, often referred to as an “electronic wallet”, which may be portable or stationary. Electronic wallets are tamper-resistant storage devices that make it difficult to commit fraud. The size of the electronic wallet depends upon the kind and amount of assets to be stored thereon.
Driven by technological advances, there is an increasing desire to conduct more commerce electronically, thereby replacing traditional asset forms (bills, coins, paper coupons, tickets, etc.) with electronic assets that represent them. A large segment of commerce is found at the low end of the value scale. This commerce involves values equivalent to present day coins (i.e., pennies, nickels, dimes, quarters, half-dollars, and dollars) and even smaller monetary units less than one cent.
Handling low value electronic assets poses some challenges. Ideally, issuing electronic assets and subsequently spending them would be as flexible as traditional paper bills and metal coins. Unfortunately, electronic assets can be easily and rapidly replicated using computers. This presents a significant risk of fraud. Criminals can reproduce the bit string of an asset and pass off the forged or counterfeited electronic assets as real. To the recipient, the counterfeit bit string offered by the criminal is identical to the expected asset bit string, rendering it difficult to detect whether the offered bit string is the original asset or a reproduced asset that has been “spent” many times before (unless multispending is done to the same payee).
To reduce the risk of fraud, limitations and restrictions are placed on how electronic assets are issued, spent, and deposited. One prior art technique, known as “Payword”, is a micropayment scheme that amortizes the processing cost of one traditional electronic coin over a whole (arbitrarily large) batch of coins (called a “stick”). Each coin in the stick has the same value. Payword, developed by Rivest and Shamir, is limited however in that the entire stick of coins must be dedicated ahead of time to a single vendor.
FIG. 1 shows three participants in an electronic asset system 20 implemented according to the Payword protocol: a user U, a bank B, and a vendor V. To briefly describe Payword, let the function Si(m), iε{U,B,V}, denote a signature of party i on message m, wherein the signature has message recovery built in. In a “Withdrawal” exchange between the bank B and the user U, the user U asks the bank B to mint L coins, dedicated to vendor V. Individual coins are derived using a random value x and a one-way hashing function h( ) as follows:                               Coin          ⁢                                          ⁢          1                =                  h          ⁡                      (            x            )                                                            Coin          ⁢                                          ⁢          2                =                  h          ⁡                      (                          h              ⁡                              (                x                )                                      )                                                            Coin          ⁢                                          ⁢          3                =                  h          ⁡                      (                          h              ⁡                              (                                  h                  ⁡                                      (                    x                    )                                                  )                                      )                                          ⋮                                    Coin          ⁢                                          ⁢          L                =                              h            L                    ⁡                      (            x            )                              
To compute a stick of coins, the bank picks the random x and computes a stick of L coins, as follows:y=hL(x)
The value y represents the bottom coin on the stick. After creating the stick of coins, the bank dedicates the stick to a single vendor and signs the stick. The bank creates a value z that contains the user's identity U, the value y, the dedicated vendor's identity V, denomination d, the number of coins in the stick L and an expiration time t at which coins will expire (i.e., z=(U,y,V,d,L,t)). The bank B signs the value z, SB (z), and returns the random x and signed stick SB (z) to the user U.
When the user pays coins to the dedicated vendor (i.e., the “Payment” exchange between the user and the vendor), the user first sends the signed stick SB (z) to the vendor. The vendor authenticates the signature. The user sends over individual coins by moving up the stick starting from the bottom stick value y. Individual coins are derived using the hashing function h( ). In this matter, the computational process of spending one or more coins from the stick is very efficient and requires little processing resources on both sides. The top coin in the stick is the random value x.
At the end of the day, the vendor deposits the highest (latest) coin received from the user (i.e., the “Deposit” exchange from the vendor to the bank). The bank credits the vendor for the stick fraction that is deposited. The user maintains credit for the remaining portion of the stick and can continue to spend it later.
Since the hashing function h( ) is one-way, the vendor cannot cheat by exceeding the highest received coin. In addition, the user cannot double spend because the stick is dedicated to one specific vendor, who is capable of rejecting double spending. The cost of a batch minting is roughly the cost of one traditional coin mint, since hashing is four orders of magnitude faster than signing. Likewise, the cost of batch deposit is roughly the cost of one traditional deposit.
Payword is limited, however, in that the stick can only be used to pay a single vendor without increased risk of fraud. This is because a vendor can easily check previous coin receipts to see if the user is trying to reveal a coin that the vendor has already seen, but multiple vendors have no easy way of comparing notes on what coins have been revealed. Thus, while Payword is efficient in terms of minting and spending coins, it is inflexible because the user is not free to spend coins coming from one stick with multiple vendors.
Accordingly, there is a need to design a system that is efficient like Payword, but is also flexible in allowing the user to spend the coins coming from one stick with multiple vendors.